package dynamicprogramming;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/3 23:17
 * https://leetcode-cn.com/problems/last-stone-weight-ii/
 */
public class LastStoneWeightII {

    /**
     * 转化为01背包问题：石块两两可以抵消，所以尽量分成同样大的两堆（最好总/2)
     * dp[i]表示容量为i的背包，能背起的最大质量为多少
     * 递推公式：dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i])
     * @param stones
     * @return
     */
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int i = 0; i < stones.length; i++) {
            sum += stones[i];
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];
        //石块
        for (int i = 0; i < stones.length; i++) {
            //背包重量
            for (int j = target; j >= stones[i]; j--) {
                //1、不放第i块石头 2、放第i块石头
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        //石堆1：dp[target]  石堆2：sum - dp[target]
        //作差  target向下取整 sum/2 > target>=dp[target]    sum>=dp[2*target]
        return sum - 2 * dp[target];
    }

    public static void main(String[] args) {

    }
}
